/**
 * 文本左右对齐
 *
 * 给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
 * 你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
 * 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
 * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
 * 注意:
 * 单词是指由非空格字符组成的字符序列。
 * 每个单词的长度大于 0，小于等于 maxWidth。
 * 输入单词数组 words 至少包含一个单词。
 *
 * 示例 1:
 * 输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
 * 输出:
 * [
 *    "This    is    an",
 *    "example  of text",
 *    "justification.  "
 * ]
 *
 * 示例 2:
 * 输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
 * 输出:
 * [
 *   "What   must   be",
 *   "acknowledgment  ",
 *   "shall be        "
 * ]
 * 解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
 *      因为最后一行应为左对齐，而不是左右两端对齐。
 *      第二行同样为左对齐，这是因为这行只包含一个单词。
 *
 * 示例 3:
 * 输入:words = ["Science","is","what","we","understand","well","enough","to",
 * "explain","to","a","computer.","Art","is","everything","else","we","do"]，maxWidth = 20
 * 输出:
 * [
 *   "Science  is  what we",
 *   "understand      well",
 *   "enough to explain to",
 *   "a  computer.  Art is",
 *   "everything  else  we",
 *   "do                  "
 * ]
 *
 * 提示:
 * 1 <= words.length <= 300
 * 1 <= words[i].length <= 20
 * words[i] 由小写英文字母和符号组成
 * 1 <= maxWidth <= 100
 * words[i].length <= maxWidth
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 题目好长, 咱先来分析下题目让咱干什么
 * 首先, 给我们一个字符串数组, 和一个每行的字符个数
 * 我们需要将这个字符数组分为很多行, 且每一行都要有 maxWidth 个字符
 * 要是字母不够的话, 用 " " 补齐, 但是这还是有一个条件的, 那就是每两
 * 字符之间用的空格要平均, 要是没法平均的话那么就要求左边比右边用的多
 * 所以我们大可以, 直接开始遍历字符串, 记录下他们的总长, 要是大于了 maxWidth
 * 就向前回溯一个, 那么大于之前的就是我们需要加入的第一层字符串了, 但是这里, 我们
 * 因为提前加入了, 所以肯定是要补上空格的, 那么咱就要算一下空格, 怎么算呢, 一开始
 * 我是想的每个字符填完之后加空格的, 但是你会发现, 这样最后面会多填空格, 我们可以
 * 在最后面特判一下, 要是到最后一个位置就不用填空格了, 然后还要注意最后一行的时候
 * 我们是加入不了的, 因为我们还不能满足条件循环就会结束, 那么我们就要提前控制最后一
 * 行字符的加入, 还有一个特那就是当我们的一行的字符只有一个的时候, 我们求要加入的空格
 * 会有一个 / 0 的报错, 所以我们也要特判一下这个情况
 * 时间复杂度 : O(n * m)
 * 空间复杂度 : O(n + m)
 */

public class Main {

    // 测试用例
    public static void main(String[] args) {
        Main test = new Main();
        String[] nums = new String[]{"Science","is","what","we","understand","well","enough","to","explain","to",
                "a","computer.","Art","is","everything","else","we","do"};
        List<String> strings = test.fullJustify(nums, 20);
    }

    public List<String> fullJustify(String[] words, int maxWidth) {

        // 这里我们用 list 记录每一行需要加入的字符, 因为后面要向着中间加入空格
        // 所以我们要提前记录需要再这一行加入的字符
        List<String> list = new ArrayList<>();

        // ans 用来保存我们的最终结果
        List<String> ans = new ArrayList<>();

        // 字符串数组长度
        int n = words.length;

        // 这里我们记录每一行的长度
        // 因为我们每个字符之间会有一个空格, 所以我们自动在
        // 每个字符前加一个空格的空间, 但是又因为 第一个 字符
        // 是不需要加入 空格的, 所以我们将前置长度置为 -1
        int currentLen = -1;

        // 遍历整个字符串数组
        for (int i = 0; i < n; i++) {

            // 这里更新当前的长度, 记得加上前面的 " "
            currentLen += words[i].length() + 1;

            // 判断是否满足条件
            if (currentLen <= maxWidth) {

                // 要是没有到达入行条件, 我们继续
                // !!!!!!!!!!!!!!!!! 但是最后一行是特殊的, 也不一定到达条件, 所以到最后一行的时候我们需要
                // 特别判断一下
                list.add(words[i]);

                // 查看是否到达最后一行
                if (i == n - 1) {

                    // 到达了, 就要加入最后一行
                    // 字符拼接函数
                    StringBuffer ret = new StringBuffer();

                    // 遍历 list 中的字符
                    for (int j = 0; j < list.size(); j++) {

                        // 这里除了第一个, 都默认前面是有个 " "
                        if (j != 0) {
                            ret.append(" ");
                        }

                        // 不管是第几个都是要加入 这个字符的
                        ret.append(list.get(j));
                    }

                    // 后面的 " " 不要忘记补上
                    for (int j = 0; j < maxWidth - currentLen; j++) {
                        ret.append(" ");
                    }

                    // 将结果加入 ans 中
                    ans.add(ret.toString());

                    // 到最后就不用清空这些值了, 因为要返回了
                }
            } else {

                // 已经满足要求

                // 这里我们想往前回溯一个, 因为这个不是这行的数据
                currentLen -= words[i].length() + 1;
                i--;

                // 字符串拼接函数
                StringBuffer ret = new StringBuffer();

                // 这里特别判断一下 list 中是否只有一个元素
                if (list.size() == 1) {

                    // 要是只有一个元素, 那也好办了, 我们直接加入就好了, 后面一样的拿 " " 补上
                    ret.append(list.get(0));

                    // 补 " "
                    for (int j = 0; j < maxWidth - currentLen; j++) {
                        ret.append(" ");
                    }

                } else {

                    // 要是不止一个 元素

                    // 我们求出没两个字符串之间需要额外加的 " "
                    // 不用考虑第一个字符串的
                    int k = (maxWidth - currentLen) / (list.size() - 1);

                    // 在考虑多出来的 " ", 应该将他们平均按顺序分给前面的 字符串中间
                    // 这样可以保证, 左边空格 不小于 右边
                    int m = (maxWidth - currentLen) % (list.size() - 1);

                    // 添加 字符串和函数
                    for (int j = 0; j < list.size(); j++) {

                        // 依旧是第一个不用 在前面加 " "
                        if (j != 0) {

                            // 不是第一个元素

                            // 先加自带的 " "
                            ret.append(" ");

                            // 再算出来的后面的 " ", 平均分下
                            for (int l = 0; l < k; l++) {
                                ret.append(" ");
                            }

                            // 记得将多余的空格分给前面的字符串中间
                            if (m != 0) {
                                ret.append(" ");
                                m--;
                            }
                        }

                        // 加入 字符串
                        ret.append(list.get(j));
                    }
                }

                // 这里要将结果加入 ans
                // 还需要将 currentLen 置为 -1
                // 将 list 清空
                ans.add(ret.toString());
                currentLen = -1;
                list.clear();
            }
        }

        // 返回结果
        return ans;
    }
}